package com.algorithm.ch1.lzr.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个序号。
 * 例如 给定 array = [2, 7, 11, 15], target = 9 因为 array[0] + array[1] = 2 + 7 = 9,所以返回 [0, 1]
 *
 * @author lzr
 * @date 2018/8/7
 */
public class TwoSum {
    public static void main(String[] args) {
        int[] array1 = {2,7,11,15};
        int[] ints1 = twoSum2(array1, 9);
        for (int i = 0; i < ints1.length; i++) {
            System.out.println(ints1[i]);
        }


    }

    /**
     * 使用map,将数组中的数值当做key1=array[i],存到map中 当map存在目标key2=target-array[i]时,代表匹配
     *
     * @param array
     * @param target
     * @return
     */
    public static int[] twoSum1(int[] array, int target) {
        int[] temp = new int[2];
        if (array == null || array.length < 2) {
            return temp;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int destValue = target-array[i];
            //由于不匹配的可能性更高, 所以先处理不匹配的条件
            if(!map.containsKey(destValue)){
                map.put(array[i],i);
            }else {
                temp[0] = map.get(destValue);
                temp[1] = i;
                break;
            }
        }
        return temp;
    }

    /**
     * 双层循环 性能低 不考虑
     * @param array
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] array, int target) {
        int[] temp = new int[2];
        if (array == null || array.length < 2) {
            return temp;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] + array[j] == target) {
                    temp[0] = i;
                    temp[1] = j;
                    break;
                }
            }
        }
        return temp;
    }

}
